package com.hanxiaozhang.no3algorithm;

import java.util.Arrays;

/**
 * 〈一句话功能简述〉<br>
 * 〈斐波那契算法〉
 * <p>
 * 斐波那契数列也称为“兔子数列”。它的重要性体现在相邻两数之比趋向黄金分割数，
 * 自然界很多现象也可找到它的身影，画图还与漂亮的螺旋线有关。定义式为：
 * *       /  0   n =0
 * * f(n) |   1   n =1
 * *      \   f(n-1) + f(n-2) n>=2
 *
 * @author hanxinghua
 * @create 2023/12/19
 * @since 1.0.0
 */
public class No14Fibonacci {

    public static void main(String[] args) {

        System.out.println(Arrays.toString(fibonacci1(10)));
        System.out.println(Arrays.toString(fibonacci2(10)));
    }


    /**
     * 斐波那契数2-动态规划
     * <p>
     * 时间复杂度：O(n)。因为，动态规划可以将重复计算的子问题缓存起来，避免重复计算。
     *
     * @param n
     * @return
     */
    private static int[] fibonacci2(int n) {
        int[] result = new int[n];

        // Tips：可以不赋值，int默认值就是0
        if (n >= 1) {
            result[0] = 0;
        }

        if (n >= 2) {
            result[1] = 1;
        }

        for (int i = 2; i < n; i++) {
            result[i] = result[i - 1] + result[i - 2];
        }
        return result;
    }


    /**
     * 斐波那契数1-递归方式
     * <p>
     * 时间复杂度：O(2^n)
     *
     * @param n 生成斐波那契数的个数
     * @return
     */
    private static int[] fibonacci1(int n) {
        int[] arr = new int[n];
        fibonacci1(n - 1, arr);
        return arr;
    }

    private static int fibonacci1(int n, int[] arr) {
        if (n < 2) {
            arr[n] = n;
            return n;
        }
        int sum = fibonacci1(n - 1, arr) + fibonacci1(n - 2, arr);
        arr[n] = sum;
        return sum;
    }


}
